var root = null

// 节点
class Node{
    constructor(value){
        this.value = value
        this.left = null
        this.right = null
    }
}

class binarySearchTree{
    constructor(){
        this.root = null
    }

    insertNode(node,newNode){
        if(newNode.value>node.value){
            if(node.right===null){
                node.right=newNode
            }else{
                this.insertNode(node.right,newNode)
            }
        }else if(newNode.value<node.value)
        {
            if(node.left===null){
                node.left=newNode
            }
            else{
                this.insertNode(node.left,newNode)
            }
        }
    }

    // 插入操作
    insert(value){
        let newNode = new Node(value)
        if(this.root===null){
            this.root=newNode
        }else{
            this.insertNode(this.root,newNode)
        }
    }

    // 搜索操作
    search(value){
        const searchNode = (value,node) => {
            if(node===null){return false}
            if(node.value===value){return true}
            return searchNode(value,value>this.node?node.right:node.left)
        }
        
        return searchNode(value,this.root)
    }

    // 查找最小值
    min(node){
        const minSize = node => {
            return node? (node.left? minSize(node.left):node):null
        }
        return minSize(node||this.root)
    }

    // 查找最大值
    max(node){
        const minSize = node => {
            return node? (node.right? minSize(node.right):node):null
        }
        return minSize(node||this.root)
    }

    // 删除值
    remove(value){
        const removeNode = (node,value) => {
            if(node === null) return null;
            if(node.value === value){
                if(node.left === null && node.right === null) return null;
                if(node.left === null) return node.right;
                if(node.right === null) return node.left;
                if(node.left !==null && node.right !==null){
                let _node = this.getMin(node.right);
                node.value = _node.value;
                node.right = removeNode(node.right,value);
                return node
                }
            } else if(value < node.value){
                node.left=removeNode(node.left,value);
                return node
            } else {
                node.right=removeNode(node.right,value);
                return node
            }
        };
        return removeNode(this.root,value)
    }


    // 中序遍历
    inOrder(){
        let Arr = new Array()
        let inOrderNode = (node,callback) => {
            if(node!==null){
                inOrderNode(node.left,callback)
                Arr.push(node.value)
                inOrderNode(node.right,callback)
            }
        }
        let callback = function(v) {
            return v
        }
        inOrderNode(this.root,callback)
        return Arr
    }

    // 先序遍历
    preOrder(){
        let Arr = new Array()
        let preOrderNode = (node,callback) => {
            if(node!==null){
                Arr.push(node.value)
                preOrderNode(node.left,callback)
                preOrderNode(node.right,callback)
            }
        }
        let callback = function(v) {
            return v
        }
        preOrderNode(this.root,callback)
        return Arr
    }

    // 后序遍历
    afOrder(){
        let Arr = new Array()
        let afOrderNode = (node,callback) => {
            if(node!==null){
                afOrderNode(node.left,callback)
                afOrderNode(node.right,callback)
                Arr.push(node.value)
            }
        }
        let callback = function(v) {
            return v
        }
        afOrderNode(this.root,callback)
        return Arr
    }
}
const bst = new binarySearchTree()
bst.insert(200);
bst.insert(150);
bst.insert(300);
bst.insert(100);
bst.insert(180);
// console.log(bst.remove())
// console.log(bst.search(180))
// console.log(bst.min())
// console.log(bst.max())
console.log(bst)
console.log(bst.inOrder())
console.log(bst.preOrder())
console.log(bst.afOrder())


